extends Object
class_name Maze
var width
var height
var visited = []
var maze = []

func generate_maze_dfs(w, h):
	width = w
	height = h
	visited = []
	maze = []
	
	# Initialize arrays
	for y in range(h):
		visited.append([])
		maze.append([])
		for x in range(w):
			visited[y].append(false)
			# [top, bottom, left, right] walls
			maze[y].append([true, true, true, true])
	
	# Start from random position
	var start_x = randi_range(0, w-1)
	var start_y = randi_range(0, h-1)
	dfs(start_x, start_y)
	
	# Ensure all cells are connected
	ensure_fully_connected()
	
	# Close outer boundaries
	close_outer_boundaries()
	
	return maze

func dfs(x, y):
	visited[y][x] = true
	var directions = [[1,0], [-1,0], [0,1], [0,-1]]
	directions = shuffle_array(directions)
	
	for dir in directions:
		var nx = x + dir[0]
		var ny = y + dir[1]
		
		# Check boundaries and if not visited
		if nx >= 0 and nx < width and ny >= 0 and ny < height and not visited[ny][nx]:
			# Remove walls between cells
			if dir[0] == 1:  # Right
				maze[y][x][3] = false  # Remove right wall
				maze[ny][nx][2] = false  # Remove left wall of neighbor
			elif dir[0] == -1:  # Left
				maze[y][x][2] = false
				maze[ny][nx][3] = false
			elif dir[1] == 1:  # Down
				maze[y][x][1] = false
				maze[ny][nx][0] = false
			elif dir[1] == -1:  # Up
				maze[y][x][0] = false
				maze[ny][nx][1] = false
			
			dfs(nx, ny)

func ensure_fully_connected():
	# Check for any unvisited cells and connect them
	for y in range(height):
		for x in range(width):
			if not visited[y][x]:
				connect_to_visited(x, y)

func connect_to_visited(x, y):
	# Find all visited neighbors
	var visited_neighbors = []
	var directions = [[1,0], [-1,0], [0,1], [0,-1]]
	
	for dir in directions:
		var nx = x + dir[0]
		var ny = y + dir[1]
		if nx >= 0 and nx < width and ny >= 0 and ny < height and visited[ny][nx]:
			visited_neighbors.append(dir)
	
	if visited_neighbors.size() > 0:
		# Randomly select one visited neighbor to connect to
		var dir = visited_neighbors[randi() % visited_neighbors.size()]
		var nx = x + dir[0]
		var ny = y + dir[1]
		
		# Remove walls between cells
		if dir[0] == 1:  # Right
			maze[y][x][3] = false
			maze[ny][nx][2] = false
		elif dir[0] == -1:  # Left
			maze[y][x][2] = false
			maze[ny][nx][3] = false
		elif dir[1] == 1:  # Down
			maze[y][x][1] = false
			maze[ny][nx][0] = false
		elif dir[1] == -1:  # Up
			maze[y][x][0] = false
			maze[ny][nx][1] = false
		
		visited[y][x] = true
		dfs(x, y)  # Continue DFS from this cell

func close_outer_boundaries():
	# Close top and bottom boundaries
	for x in range(width):
		maze[0][x][0] = true  # Top wall of top row
		maze[height-1][x][1] = true  # Bottom wall of bottom row
	
	# Close left and right boundaries
	for y in range(height):
		maze[y][0][2] = true  # Left wall of left column
		maze[y][width-1][3] = true  # Right wall of right column

func shuffle_array(array):
	# Fisher-Yates shuffle
	var shuffled = array.duplicate()
	for i in range(shuffled.size() - 1, 0, -1):
		var j = randi() % (i + 1)
		var temp = shuffled[i]
		shuffled[i] = shuffled[j]
		shuffled[j] = temp
	return shuffled
